package sort.test4_11;

public class HeapSort {

    public int[] heapSort(int[] nums){
        if (nums.length==0){
            return  null;
        }
        int length = nums.length;
        for (int i=length/2+1; i >=0 ; i--) {
            adjustHeap(nums,i, nums.length);
        }
        for (int i = length-1; i >0 ; i--) {
            int temp=nums[i];
            nums[i]=nums[0];
            nums[0]=temp;
            adjustHeap(nums,0,i);
        }
        return  nums;
    }

    public void  adjustHeap(int[] nums, int k,int length){
        int temp=nums[k];
        for (int i=2*k+1 ; i <length ; i=2*i+1) {
            if (i+1< length&&nums[i]<nums[i+1]){
                i++;
            }
            if (nums[i]>temp){
                nums[k]=nums[i];
                k=i;
            }else {
                break;
            }
        }
        nums[k]=temp;
    }

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] a={1,5,3,9,4,7};
        heapSort.heapSort(a);
        for (int b: a
        ) {
            System.out.println(b);

        }

    }






}
